package leetcode.code881.BoatstoSavePeople;

public class Solution88103 extends BoatstoSavePeople {

	@Override
	public int numRescueBoats(int[] people, int limit) {
		mergeSort(people, 0, people.length - 1);
		int lp = 0;
		int rp = people.length - 1;
		int count = 0;
		while (lp <= rp) {
			if (people[lp] + people[rp] <= limit) {
				lp++;
			}
			count++;
			rp--;
		}
		return count;
	}

	public void mergeSort(int[] array, int l, int r) {
		if (l == r)
			return;
		int m = (r - l) / 2 + l;
		mergeSort(array, l, m);
		mergeSort(array, m + 1, r);
		merge(array, l, r);
	}

	public void merge(int[] array, int l, int r) {
		int size = r - l + 1;
		int[] temp = new int[size];
		int m = (r - l) / 2 + l;
		int n = m + 1;
		int p = 0;
		int lp = l;
		while (lp <= m && n <= r) {
			temp[p++] = array[lp] < array[n] ? array[lp++] : array[n++];
		}
		while (lp <= m) {
			temp[p++] = array[lp++];
		}
		while (n <= r) {
			temp[p++] = array[n++];
		}
		for (int i = 0; i < size; i++) {
			array[l++] = temp[i];
		}
	}

	public static void main(String[] args) {
		Solution88103 so = new Solution88103();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
